# -*- coding:utf-8 -*-

'''
输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。
假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。
'''

# 树节点
class TreeNode:                     
    def __init__(self, elem, left_child=None, right_child=None):
        self.elem = elem
        self.left = left_child
        self.right = right_child

# 实现一个简易队列
class Queue:
    def __init__(self):
        self.elems = []
 
    def is_empty(self):
        return len(self.elems) == 0
 
    def enqueue(self, elem):
        self.elems.append(elem)
 
    def dequeue(self):
        if len(self.elems) == 0:
            return None
        return self.elems.pop(0)
 
def reConstructBinaryTree(pre_tree, in_tree):
    if len(pre_tree) == 0:
        return None
    if len(pre_tree) == 1:
        return TreeNode(pre_tree[0])
    else:
        root = TreeNode(pre_tree[0])
        #左子树
        root.left = reConstructBinaryTree(pre_tree[1:in_tree.index(pre_tree[0])+1], in_tree[:in_tree.index(pre_tree[0])])
        #右子树
        root.right = reConstructBinaryTree(pre_tree[in_tree.index(pre_tree[0])+1:], in_tree[in_tree.index(pre_tree[0])+1:])
        return root
    
def printBinaryTree(rootQueue):
    while True:
        # 采用层序遍历
        x = rootQueue.dequeue()          
        print(x.elem)
        if x is not None:
            if x.left is not None:
                rootQueue.enqueue(x.left)
            if x.right is not None:
                rootQueue.enqueue(x.right)
        if rootQueue.is_empty():
            break
        
 
pre_tree = [1, 2, 4, 7, 3, 5, 6, 8]
tin_tree = [4, 7, 2, 1, 5, 3, 8, 6]
    
root = reConstructBinaryTree(pre_tree, tin_tree)
# 创建队列
rootQueue = Queue()
rootQueue.enqueue(root)
i = 0

printBinaryTree(rootQueue)
